All the dp problem is kinda similar, this is marked at hard, but in reality it is backtrack question possible sub array partition with little modification.
class Solution {
int[] memo;
int MOD = 1000000007;
public int numberOfArrays(String s, int k) {
memo = new int[s.length() + 1];
Arrays.fill(memo,-1);
return dp(s,k,0);
}
private int dp(String s, int k, int curr){
// base case
if(curr == s.length()) return 1; // we have no more possible number to play with
if(s.charAt(curr) == '0') return 0; // leading zero
// solved case
if(memo[curr] != -1) return memo[curr];
// start res with 0
int res = 0;
for(int i = curr; i < s.length(); i ++){
// try pairtition at every possible point
String num = s.substring(curr,i + 1);
// if num > k then we know we cant have this number
if (Long.parseLong(num) > k)
break;
// add to res if we made to the end (+ 1) res
res = (res + dp(s,k,i + 1)) % MOD;
}
return memo[curr] = res;
}
}